1. Field of the Invention
The present invention generally relates to adding circuits and, more particularly, to an adding circuit for adding binary numbers and an accumulator for adding binary numbers sequentially supplied thereto in an accumulation fashion wherein high speed addition and accumulation can be executed without increasing the circuit scale thereof too much.
2. Description of the Prior Art
As an adding circuit for adding binary numbers (a.sub.n-1, . . . a.sub.1, a.sub.0) and (b.sub.n-1, . . . b.sub.1, b.sub.0) of n bits (n is an integer larger than 2) to provide binary numbers (c.sub.n, . . . c.sub.1, c.sub.0) of (n+1) bits, the most popular adding circuit is formed of one half adder and (n-1) full adders.
FIG. 1 shows an example of such prior-art adding circuit, wherein n=16.
As shown in FIG. 1, this adding circuit comprises a half adder 1 and full adders 2. In this popular adding circuit, carry data of the half adder of least significant bit (LSB) is gradually propagated to the full adders of most significant bit (MSB) to first provide accurate calculated results. Therefore, t assumes a calculation time of one full adder. Then, the total calculation time T.sub.1 for adding binary number of n bits is expressed by the following equation (1): EQU T.sub.1 .apprxeq.n t (1)
Accordingly, if n is increased too much, a lot of calculation time is required depending on the calculation purpose.
In order to realize the high speed addition, an adding circuit of carry select adder system is proposed. FIG. 2 shows an example of the previously-proposed carry select adder type adding circuit in which n=16, by way of example.
As shown in FIG. 2, carry look ahead circuits 3A to 3D of 4 bits are connected in cascade to calculate beforehand only carry data at high speed. Adders 4A to 4D of 4 bits are provided to perform the addition assuming that carry data from less significant bits are "0", whereas adders 5B to 5D of 4 bits are provided to perform the addition assuming that carry data from less significant bits are "1". Multiplexer circuits 6B to 6D are employed as switching circuits.
The adder 4A adds 0'th to 3rd binary numbers (a.sub.3. . . a.sub.0 and b.sub.3. . . b.sub.0) of two binary numbers, the adder 4B adds binary numbers of 4th to 7th bits (a.sub.7. . . a.sub.4 and b.sub.7. . . b.sub.4) assuming that carry data from less than 3 bits are "0", and the adder 5B adds binary numbers of 4th to 7th bits assuming that the carry data from less than 3 bits are "1". By selecting the added result of the adder 4B or 5B by using the multiplexer 6B in response to whether the carry data from the carry look ahead circuit 3A is "0" or "1", the added result of binary numbers of 4th to 7th bits (c.sub.7. . . c.sub.4) can be obtained accurately. In the same fashion, added results (c.sub.15 to c.sub.8) of 8th to 15th bits of the binary numbers can be obtained accurately, and a value c.sub.16 of 16th bit can be obtained as carry data of the carry look ahead circuit 3D of the most significant bit.
Accordingly, a total calculation time required to perform the addition of binary numbers in the example of FIG. 2 becomes substantially equal to the calculation time of the 4-bit adder 4B or 5B. In the adding circuit of the carry select adder system, assuming that the calculation time of one carry look ahead circuit 3A, 3B and so on is selected to be t which is the calculation time of one 1-bit full adder and that k carry look ahead circuits, i.e., k m-bit adders are utilized, then a total calculation time T.sub.2 required to add binary numbers of n (=km where m is an integer) bits is expressed as: EQU T.sub.2 .apprxeq.kt (in the case of k.gtoreq.m) (2A) EQU or EQU T.sub.2 .apprxeq.mt (in the case of k&lt;m) (2B)
It is to be appreciated from the foregoing equations (2A) and (2B) that, as compared with the case of the standard adding circuit (see equation (1)), this can perform the calculation at speed as high as m times to k times.
In the adding circuit of the carry select adder system, a circuit block 7D assumes a circuit formed of, for example, the adding circuits 4D and 5D and the multiplexer 6D. Then, an adding circuit which modifies the circuit block 7D is proposed as shown in FIG. 3. The technical report (Vol. 89, No. 4, PP. 37 to 44) of the Institute of Electronics, Informations and Communication Engineers describes this type of adding circuit.
Referring to FIG. 3, the 4-bit adding circuit 5D (see FIG. 2) for adding binary numbers is replaced with an adding circuit 8D for adding 1 to a binary number of 4 bits. This adding circuit 8D is interposed between the output port of the adder 4D and one input port of the multiplexer 6D. In that case, the calculation time at the adder 8D is added so that a total calculation time T.sub.3 is expressed as: EQU T.sub.3 .apprxeq.kt (in the case of k.gtoreq.2m) (3A) EQU or EQU T.sub.3 .apprxeq.2mt (in the case of k&lt;2m) (3B)
Although the calculation speed of the adding circuit of the carry select adder type can be increased as described above, this adding circuit needs the addition of the multiplexers 6B to 6D, which unavoidably makes the circuit scale large.
Further, if the circuit block of the example shown in FIG. 3 is employed, then the calculation speed is decreased to be substantially one half as compared with the original carry select adder type. In that case, however, the adding circuit 5D is replaced with the adding circuit 8D, which provides a reduced circuit scale. Even this circuit needs the multiplexers 6B to 6D, and there remains the substantial disadvantage that the circuit scale is very large.
FIG. 4 shows an arrangement of a prior-art accumulator which accumulatively adds (i.e., accumulates) numbers x (x.sub.n-1. . . x.sub.1, x.sub.0) of less than n bits sequentially supplied thereto to obtain a sum s (s.sub.n-1. . . s.sub.1, s.sub.0) of n bits.
With reference to FIG. 4, an n-bit adder 201 is constructed by connecting a single 1-bit half adder 202.sub.0 and (n-1) 1-bit full adders 202.sub.1 to 202.sub.n-1. Delay registers 203.sub.0 to 203.sub.n-1 are shown to have clear terminals CLR and clock terminals CK. Sum outputs of the adders 202.sub.0 to 202.sub.n-1 are respectively supplied to input terminals of the registers 203.sub.0 to 203.sub.n-1, data x.sub.0 to x.sub.n-1 of respective carries of numbers x are respectively supplied to first input terminals of the adders 202.sub.0 to 202.sub.n-1, and delayed outputs of the registers 203.sub.0 to 203.sub.n-1, are supplied to the other input terminals of the adders 202.sub.0 to 202.sub.n-1, respectively.
When the accumulative addition is carried out by the accumulator in the example of FIG. 4, a reset signal R is supplied to the clear terminals CLR of the registers 203.sub.0 to 203.sub.n-1 to reset the output data of these registers 203.sub.0 to 203.sub.n-1 to zero. Then, the number x supplied to the n-nit adder 201 is updated at a predetermined cycle and a clock pulse .phi.1 of this predetermined cycle is supplied to the clock terminals CK of the registers 203.sub.0 to 203.sub.n-1. Thus, the output of the n-bit adder 201 provides data S.sub.0 to S.sub.n-1 of respective carries of the sum s of n bits. In that case, the carry output from the n'th bit which is the most significant bit of the n-bit adder 201 to the (n+1) bits can be neglected.
In the n-bit adder 201, however, the accurate sum output is not obtained until the carry output of the half adder 202.sub.0 propagates up to the full adder 202.sub.n-1. There is then the substantial disadvantage that, when the value n is increased, then the calculation speed is decreased. Assuming that T is calculation time of the one 1-bit half adder or full adder, a calculation time required by the accumulator of the example FIG. 4 to perform one calculation is expressed as nearly nT.
Japanese Patent Laid-Open Gazette No. 64-86271 describes another accumulator wherein regardless of the increase of the value n, a calculation time thereof is always substantially equal to the calculation time T of the single 1-bit full adder. This previously-proposed accumulator cannot avoid such a disadvantage that the circuit scale thereof still remains large. Further, it is frequently observed that the calculation speed is not always increased to the extent of the single 1-bit full adder.